
#construct adjacency list from the file:
def graph_from_file file
  
  count_lines = %x{wc -l #{file}}.split.first.to_i
  nodes = Hash.new
  count_lines.times {|i| nodes[i+1] = []}
  edges = Array.new
  File.open(file).each_line{ |line|
    arr = line.split.map {|x| x.to_i}
    node_num = arr.shift
    #nodes[node_num] = []
    arr.each do |other_node|
      new_edge = [node_num, other_node]
      if node_num < other_node
        nodes[node_num] << new_edge
        nodes[other_node] << new_edge
        edges << new_edge
      end
    end
  }
  return {:nodes => nodes, :edges => edges}
end


#single iteration of randomized karger algorithm:
#input graph is represented with two adjacency lists:
#nodes - hash { node_number => [edge1, edge2,....]}
#edges - array[[node1,node2], [node1,node2]....]
#every edge [node1,node2] referenced from nodes hash has only one copy in edges array
def random_mincut (nodes, edges) #input graph is given as adjacency list
  return -1 if nodes.size <=1
  contraction_map = Hash.new{|hash,key| hash[key] = [key]}
  while nodes.size > 2
    #pick up random node_fused and random edge_removed among edges of node_fused
    node_fused = nodes.keys[rand(nodes.size)]
    edge_removed = nodes[node_fused][rand(nodes[node_fused].size)]
    
    node_removed = (edge_removed[0] != node_fused ? edge_removed[0] : edge_removed[1])
    
    #contracting
    edges_from_node_removed = nodes[node_removed]
    edges_from_node_removed.each do |edge|
      modify_idx = (edge[0] == node_removed ? 0 : 1)
      
      edge[modify_idx] = node_fused
      if edge[0] == edge[1] #need to remove the edge
        #remove from array of edges
        edges.delete_at(edges.find_index(edge))
      else
        nodes[node_fused] << edge
      end
    end
    #cleanup cycled-edges
    nodes[node_fused].keep_if {|edge| edge[0] != edge[1]}
    nodes.delete(node_removed)
    #rememeber what we have merged, to show final cut
    contraction_map[node_fused] += contraction_map[node_removed]
  end
  return edges.size, contraction_map[nodes.keys[0]], contraction_map[nodes.keys[1]]
end

graph = graph_from_file 'C:\Users\kirill\Documents\Standford_couses\algo\kargerAdj.txt'

1.times {
  mincut = [graph[:edges].size, 0, 0]
  100.times do
    input = Marshal.load(Marshal.dump(graph))
    new_cut, left_part, right_part = random_mincut(input[:nodes], input[:edges])
    mincut = [new_cut, left_part, right_part] if new_cut < mincut[0]
  end
  mincut[1], mincut[2] = mincut[2], mincut[1] if mincut[1].size > mincut[2].size
  mincut[1].sort!
  mincut[2].sort!
  p "mincut = #{mincut}"
}

puts "Enter a value :"
val = readline
puts val


#TODO:
#show the partition of the graph
